`
https://leetcode.cn/problems/minimum-genetic-mutation/
`

/**
 * @param {string} startGene
 * @param {string} endGene
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (startGene, endGene, bank) {
  const bankSet = new Set(bank)
  // 基因库里没有目标基因
  if (!bankSet.has(endGene)) {
    return -1
  }

  // 当前操作数
  let step = 0

  const q = [startGene]
  const visited = new Set()
  visited.add(startGene)

  // BFS
  while (q.length) {
    // 一层层遍历，每一层就是一次操作
    const sz = q.length
    for (let i = 0; i < sz; i++) {
      const cur = q.shift()
      if (cur === endGene) {
        return step
      }
      // 向周围扩散
      for (const gene of getAllPermutation(cur)) {
        // 如果基因没用过且在基因库里
        if (!visited.has(gene) && bankSet.has(gene)) {
          visited.add(gene)
          q.push(gene)
        }
      }
    }
    // 本层遍历完，操作 +1
    step++
  }

  return -1
};

// 生成所有该基因的一次基因变化可能
function getAllPermutation(gene) {
  const res = []
  const geneChars = gene.split('')
  for (let i = 0; i < geneChars.length; i++) {
    const oldChar = geneChars[i]
    for (const newChar of ['A', 'C', 'G', 'T']) {
      geneChars[i] = newChar
      res.push(geneChars.join(''))
    }
    geneChars[i] = oldChar
  }
  return res
}